/*
题目地址:https://leetcode-cn.com/problems/fraction-to-recurring-decimal/
题目标签:数学,哈希表(unordered),字符串
*/

#include <iostream>
#include <string>
using std::string;
using std::to_string;

#include <unordered_map>
using std::unordered_map;

class Solution {
   public:
    string fractionToDecimal(int numerator, int denominator) {
        // 预处理长度超出的情况
        long numeratorLong = (long)numerator;
        long denominatorLong = (long)denominator;

        // 预处理没有小数部分的情况
        if (numeratorLong % denominator == 0) {
            return to_string(numeratorLong / denominatorLong);
        }

        string ans = "";

        // ---------- 处理负数的情况 ----------
        if (numeratorLong < 0 ^ denominatorLong < 0) {
            ans += "-";
        }
        numeratorLong = abs(numeratorLong);
        denominatorLong = abs(denominatorLong);

        // ---------- 计算整数部分 ----------
        ans += to_string(numeratorLong / denominatorLong) + ".";
        long rem = numeratorLong % denominatorLong;  // 计算当前余数

        // ---------- 计算小数部分 ----------
        string faction;                   // 小数部分
        unordered_map<long, int> remMap;  // 余数与出现的小数位的哈希表
        int idx = 0;                      // 当前小数位
        while (true) {
            // 处理有限小数的情况
            if (rem == 0) {
                return ans + faction;
            }

            //处理找到循环节的情况
            if (remMap.count(rem)) {
                int start = remMap[rem];
                return ans + faction.substr(0, start) + "(" +
                       faction.substr(start) + ")";
            }

            remMap[rem] = idx;  //将当前位余数添加到哈希表

            rem *= 10;  // 更新当前位的余数
            faction += to_string(rem / denominatorLong);  // 计算当前小数位的值
            rem = rem % denominatorLong;  //计算下一位的余数

            ++idx;
        }
    }
};

int main() {
    Solution solution;
    std::cout << solution.fractionToDecimal(1, 2) << std::endl;    // "0.5"
    std::cout << solution.fractionToDecimal(2, 1) << std::endl;    // "2"
    std::cout << solution.fractionToDecimal(2, 3) << std::endl;    // "0.(6)"
    std::cout << solution.fractionToDecimal(4, 333) << std::endl;  // "0.(012)"
    std::cout << solution.fractionToDecimal(1, 5) << std::endl;    // "0.2"
}